#pragma once

#include "list.h"
#include "if_tool.h"

template<typename list1, typename list2>
struct merge
{
   typedef typename if_tool<
      (list1::head_) < (list2::head_),
      list_t<
         list1::head_, 
         typename merge<
            typename list1::tail_,
            list2
         >::result_
      >,
      list_t<
         list2::head_,
         typename merge<
            list1,
            typename list2::tail_
         >::result_
      >
   >::result_ result_;
};

template<typename list>
struct merge<list, empty_list_t>
{
   typedef list result_;
};

template<typename list>
struct merge<empty_list_t, list>
{
   typedef list result_;
};

template<typename list>
struct sort
{
   typedef typename merge<
      typename sort<
         typename prefix<
            length<list>::length_ / 2,
            list
         >::result_
      >::result_,
      typename sort<
         typename
         suffix<
            length<list>::length_ / 2,
            list
         >::result_
      >::result_
   >::result_ result_;
};

template<>
struct sort<empty_list_t>
{
   typedef empty_list_t result_;
};

template<int value>
struct sort<list_t<value, empty_list_t>>
{
   typedef list_t<value, empty_list_t> result_;
};